Celestin Apprentice 5/Apprentice-Release5.iso/Source Code/C/Games/Abalone 1.4.2/src/Compute.c

C/C++ Source or Header | 1995-09-21 | 19.3 KB | 768 lines | [TEXT/MPS ]

#define COMPUTE_C
#include "Compute.h"
#undef COMPUTE_C


#pragma segment More


//    There are several methods to find the best move to make.
//    A general and simple case is FindBestBoard;
//    FindBestMove is just a slightly more efficient special-case version.
//    FindBestBoard iterates over all the valid moves,
//    using a standard minimax strategy with a recursion level specified as in level,
//    to find the move that gives the best (or next best) result.
//    The easiest and most general way to implement a new strategy is to make a BoardJudgeProc.
//    The function TheFinalStrategy right below is all yours to try this,
//    but first read more about the conventions used in this program.

static unsigned char search_order [kFields+1] =
{
     1,     2,     3,     4,     5,    11,    18,    26,    35,    43,    50,    56,    61, 60,    59,    58,    57,    51,    44,    36, 27,    19,    12,    6,
    31,
    22,    23,    32,    40,    39,    30,
    14,    15,    16,    24,    33,    41,    48,    47,    46,    38,    29,    21,
     7,     8,     9, 10,    17,    25,    34,    42,    49,    55,    54,    53,    52,    45,    37,    28,    20,    13,
    0    //    0 = sentinel
};

static unsigned char fliche_seek[kDirections][3] =
{
    {2, 3, 0},
    {1, 3, 0},
    {1, 2, 0},
    {2, 3, 0},
    {1, 3, 0},
    {1, 2, 0}
};


static MoveData scratch;


typedef struct _eval
{
    short        value;
    MoveData    move;

}    Eval, *EvalPtr;


static Eval        theEvals [16 * 6 * 3];    //    Size >= theoretical max. # of moves.


short
GenerateMoves (BoardPtr board, BoardJudgeProc judgeboard, short player, short level)
{
    Board        whatIfBoard;
    MoveData     m;
    short        index = 0;
    FieldsPtr    fp;

    for (fp = search_order, m[0] = *fp; *fp; m[0] = *++fp)
    {
        if (board->field[m[0]] != player)
            continue;

        for (m[3] = right; m[3] < down; m[3]++)
        {
            register unsigned char *fd;
            register unsigned char    df;

            m[1] = empty;

            if (ValidMove (board, m))
            {
                CopyBoard (board, & whatIfBoard);

                (void) DoMove (& whatIfBoard, m);
                *((long *) theEvals[index].move) = *((long *) m);
                theEvals[index++].value = (*judgeboard) (& whatIfBoard, player);
            }

//            if (level == 0 && (gSet.Level[gTheGame.CurrentPlayer] % 1))
//                continue;

            for (fd = fliche_seek[m[3]], df = *fd; *fd; df = *fd++)
            {
                m[1] = Neighbour (m[0], df);

                if (board->field[m[1]] != player)
                    continue;

                m[2] = empty;

try_fliche_3_3:    if (ValidFlicheMoveSorted (board, m))
                {
                    CopyBoard (board, & whatIfBoard);

                    (void) DoFlicheMove (& whatIfBoard, m);

                    *((long *) theEvals[index].move) = *((long *) m);
                    theEvals[index++].value = (*judgeboard) (& whatIfBoard, player);
                }

                if (! m[2])
                {
                    m[2] = Neighbour (m[1], df);

                    if (board->field[m[2]] == player)    //    a fliche of length 3 in this direction
                        goto try_fliche_3_3;
                }
            }
        }
    }
    return index;
}



int
CompareEvals (const void *e1, const void *e2)
{
    return *((short *) e2) - *((short *) e1);
}



void
SortMoves (short n_moves)
{
    qsort (theEvals, n_moves, sizeof (Eval), CompareEvals);
}



short
FindNiceBoard (BoardPtr board, BoardJudgeProc judgeboard, short player, MovePtr move, short level)
{
#    define                 SEARCH_WIDTH    5

    Board                whatIfBoard;
    short                whatIfResult;
    short                maxSoFar = kMinJudgeVal;

    short                n_moves;
    register short        i;
    Eval                tmpEval[SEARCH_WIDTH];

    if (gInterrupted)
        return kMinJudgeVal;

    n_moves = GenerateMoves (board, judgeboard, player, level);

    if (level <= 0)
    {
        register short    besti = 0;

find_nice_1:

        for (i = 0; i < n_moves; i++)
            if (theEvals[i].value > theEvals[besti].value)
                besti = i;

        if (MoveIsKO (theEvals[besti].move, 0, player))
        {
        //    The move we think nicest is a KO move, so we pick our second choise.

            theEvals[besti].value = kMinJudgeVal;
            goto find_nice_1;
        }

        * ((long *) move) = * ((long *) (theEvals[besti].move));
        return theEvals[besti].value;
    }

    qsort (theEvals, n_moves, sizeof (Eval), CompareEvals);

////    Alternative special case level == 0
//    if (level <= 0)
//    {
//        * ((long *) move) = * ((long *) (theEvals[0].move));
//        return theEvals[0].value;
//    }

    memcpy (tmpEval, theEvals, SEARCH_WIDTH * sizeof (Eval));

    * ((long *) move) = 0L;    //    initialise (=invalidate) the move

    for (i = 0; i < SEARCH_WIDTH; i++)
    {
        SystemTime();

        if (gInterrupted)
            return kMinJudgeVal;

        CopyBoard (board, & whatIfBoard);

        if (tmpEval[i].move[1])
            (void) DoFlicheMove (& whatIfBoard, tmpEval[i].move);
        else
            (void) DoMove (& whatIfBoard, tmpEval[i].move);

        whatIfResult
        =    - FindNiceBoard (    & whatIfBoard,
                                judgeboard,
                                NextPlayer (player),
                                scratch,
                                level - 1
                            );

        if (whatIfResult > maxSoFar)
        {
            if    (    ! (level == gSet.Level[gTheGame.CurrentPlayer]
                    &&    MoveIsKO (tmpEval[i].move, level, player))
                )
            {
                maxSoFar = whatIfResult;    //    best move so far!
                * ((long *) move) = * ((long *) (tmpEval[i].move));
            }
        }
    }
    return maxSoFar;
}


//    The following finds the best move it can make, using a given BoardJudgeProc.
//    You can use this unchanged for a standard MiniMax strategy with pruning,
//    or you can modify it to use a different strategy, but you're on your own if you do this.
//    If you do implement a new search method, you should also modify AutoPlay in Board.c.

short
FindBestBoard (BoardPtr board, BoardJudgeProc judgeboard, short player, MovePtr move, short level, PruneJudgeProc prunemove, short alfa, short beta)
{
    MoveData             m;
    register FieldsPtr    fp;

    Board                whatIfBoard;
    short                whatIfResult;
    short                minSoFar = kMaxJudgeVal;
    short                maxSoFar = kMinJudgeVal;

    if (gInterrupted)
        return kMinJudgeVal;

    * ((long *) move) = 0L;    //    initialise (=invalidate) the move

//    Generate all possible moves to find the best one.
//    Field search order as specified in array search_order;
//    contains what seems to be a profitable order for alpha-beta pruning.

    for (fp = search_order, m[0] = *fp; *fp; m[0] = *++fp)
    {
        if (board->field[m[0]] != player)    //    no ball to play on this field, try next field
            continue;

        if (level == 1)
            SystemTime();

        if (gInterrupted)
            return kMinJudgeVal;


    //    Field m[0] is owned by the current player.

        for (m[3] = right; m[3] < down; m[3]++)    //    Try moves in all directions
        {
            register unsigned char     *fd;
            register unsigned char     df;

        //    Straight moves go first.
        //    (Straight moves are generally more profitable than fliche moves.)

            m[1] = 0;    //    Show this is not a fliche move

            if (ValidMove (board, m))
            {
                CopyBoard (board, & whatIfBoard);

                (void) DoMove (& whatIfBoard, m);

                if (level <= 0 || prunemove != NULL)
                {
                //    Need to compute the judgement of this board,
                //    either as a parameter for the pruning function or as the final result.

                    whatIfResult = (*judgeboard) (& whatIfBoard, player);
                }

                if    (    level > 0
                    ||    prunemove == NULL
                    ||    !((*prunemove) (level, whatIfResult, maxSoFar))
                    )

                    whatIfResult = (level <= 0)
                        ?    (*judgeboard) (& whatIfBoard, player)
                        :     - FindBestBoard (    & whatIfBoard,
                                                judgeboard,
                                                NextPlayer (player),
                                                scratch,
                                                level - 1,
                                                prunemove,
                                                alfa,
                                                beta
                                            );

                if (whatIfResult > maxSoFar)
                {
                    if (! (level == gSet.Level[gTheGame.CurrentPlayer] && MoveIsKO (m, level, player)))
                    {
                        if (whatIfResult > maxSoFar)    //    best move so far!
                            * ((long *) move) = * ((long *) (& m));

                        if (AlfaBeta (player, whatIfResult, &minSoFar, &maxSoFar, &alfa, &beta))
                            return player == gTheGame.CurrentPlayer ? minSoFar : maxSoFar;
                    }
                }
            }
        //    Now the fliche moves.

        //    m[3]    ::= the direction the fliche moves to
        //    df        ::= the direction of the fliche itself.
        //    only the first 3 directions need to be tested for df

            for (fd = fliche_seek[m[3]], df = *fd; *fd; df = *fd++)
            {
            //    For the first three directions that are not aligned with the fliche...

                m[1] = Neighbour (m[0], df);

            //    it is OK to speak about fliche moves of length 1,
            //    but these are just the same as ordinary moves and are handled above.

                if (board->field[m[1]] != player)    //    no fliche of length 2 in this direction...
                    continue;                        //    ...so there won't be one of length 3 either

            //    a fliche of lenght 2 exists.
            //    now test if we can move it (in direction m[3]), and what this would bring us

                m[2] = empty;

try_fliche_3_2:    if (ValidFlicheMoveSorted (board, m))
                {
                    CopyBoard (board, & whatIfBoard);

                    (void) DoFlicheMove (& whatIfBoard, m);

                    if (level <= 0 || prunemove != NULL)

                        whatIfResult = (*judgeboard) (& whatIfBoard, player);

                    if    (    level > 0
                        ||    prunemove == NULL
                        ||    !((*prunemove) (level, whatIfResult, maxSoFar))
                        )

                        whatIfResult = (level <= 0)
                            ?    (*judgeboard) (& whatIfBoard, player)
                            :     - FindBestBoard (    & whatIfBoard,
                                                    judgeboard,
                                                    NextPlayer (player),
                                                    scratch,
                                                    level - 1,
                                                    prunemove,
                                                    alfa,
                                                    beta
                                                );

                    if (whatIfResult > maxSoFar)
                    {
                        if (! (level == gSet.Level[gTheGame.CurrentPlayer] && MoveIsKO (m, level, player)))
                        {
                            if (whatIfResult > maxSoFar)    //    best move so far!
                                * ((long *) move) = * ((long *) (& m));

                            if (AlfaBeta (player, whatIfResult, &minSoFar, &maxSoFar, &alfa, &beta))
                                return player == gTheGame.CurrentPlayer ? minSoFar : maxSoFar;
                        }
                    }

                }

            //    if there is a third ball for this fliche, try the fliche of length 3 as well

                if (! m[2])        //    Wait a minute! Didn't we just do this ?
                {
                    m[2] = Neighbour (m[1], df);

                    if (board->field[m[2]] == player)    //    a fliche of length 3 in this direction
                        goto try_fliche_3_2;

                }
            }
        }
    }
    return maxSoFar;
}




//    Same as FindBestBoard, but with some clever (?) search ordering
//    and with lowest-level fliche moves all pruned out.

short
FindGoodBoard (BoardPtr board, BoardJudgeProc judgeboard, short player, MovePtr move, short level, PruneJudgeProc prunemove, short alfa, short beta)
{
    MoveData             m;
    register FieldsPtr    fp;
    register short         df;

    Board                whatIfBoard;
    short                whatIfResult;
    short                minSoFar = kMaxJudgeVal;
    short                maxSoFar = kMinJudgeVal;

    if (gInterrupted)
        return kMinJudgeVal;

    * ((long *) move) = 0L;    //    initialise (=invalidate) the move

    for (fp = search_order, m[0] = *fp; *fp; m[0] = *++fp)
    {
        if (board->field[m[0]] != player)    //    no ball to play on this field, try next field
            continue;

        if (level == 1)
            SystemTime();

        if (gInterrupted)
            return kMinJudgeVal;

    //    Field m[0] is owned by the current player

        for (m[3] = right; m[3] < down; m[3]++)    //    Try moves in all directions
        {
        //    Straight moves go first.

            m[1] = 0;    //    Show this is not a fliche move.

            if (ValidMove (board, m))
            {
                CopyBoard (board, & whatIfBoard);

                (void) DoMove (& whatIfBoard, m);

                if (level <= 0 || prunemove != NULL)

                    whatIfResult = (*judgeboard) (& whatIfBoard, player);


                if    (    level > 0
                    ||    prunemove == NULL
                    ||    !((*prunemove) (level, whatIfResult, maxSoFar))
                    )

                    whatIfResult = (level <= 0)
                        ?    (*judgeboard) (& whatIfBoard, player)
                        :     - FindGoodBoard (    & whatIfBoard,
                                                judgeboard,
                                                NextPlayer (player),
                                                scratch,
                                                level - 1,
                                                prunemove,
                                                alfa,
                                                beta
                                            );

                if (whatIfResult > maxSoFar)
                {
                    if (! (level == gSet.Level[gTheGame.CurrentPlayer] && MoveIsKO (m, level, player)))
                    {
                        if (whatIfResult > maxSoFar)    //    best move so far!
                            * ((long *) move) = * ((long *) (& m));

                        if (AlfaBeta (player, whatIfResult, &minSoFar, &maxSoFar, &alfa, &beta))
                            return player == gTheGame.CurrentPlayer ? minSoFar : maxSoFar;
                    }
                }
            }

            if (level == 0 && (gSet.Level[gTheGame.CurrentPlayer] % 1))

            //    Skip all fliche moves if we move last! Now that's pruning!

                continue;

        //    And now the fliche moves.

        //    m[3]    ::= the direction the fliche moves to
        //    df        ::= the direction of the fliche itself
        //    only the first 3 directions need to be tested for df

            for (df = right; df < left; df++)
            {
            //    skip 'fliche' moves along axis of fliche:
            //    these are ordinary moves and are handled above.

                if (m[3] == df || m[3] == df + 3)    //    along axis of fliche
                    continue;

                m[1] = Neighbour (m[0], df);

            //    it is OK to speak about fliche moves of length 1,
            //    but these are just the same as ordinary moves and are handled above.

                if (board->field[m[1]] != player)    //    no fliche of length 2 in this direction...
                    continue;                        //    ...so there won't be one of length 3 either

            //    A fliche of lenght 2 exists.
            //    now test if we can move it (in direction m[3]), and what this would bring us.

                m[2] = empty;

try_fliche_3_1:    if (ValidFlicheMoveSorted (board, m))
                {
                    CopyBoard (board, & whatIfBoard);

                    (void) DoFlicheMove (& whatIfBoard, m);

                    if (level <= 0 || prunemove != NULL)

                        whatIfResult = (*judgeboard) (& whatIfBoard, player);

                    if    (    level > 0
                        ||    prunemove == NULL
                        ||    !((*prunemove) (level, whatIfResult, maxSoFar))
                        )

                        whatIfResult = (level <= 0)
                            ?    (*judgeboard) (& whatIfBoard, player)
                            :     - FindGoodBoard (    & whatIfBoard,
                                                    judgeboard,
                                                    NextPlayer (player),
                                                    scratch,
                                                    level - 1,
                                                    prunemove,
                                                    alfa,
                                                    beta
                                                );

                    if (whatIfResult > maxSoFar)
                    {
                        if (! (level == gSet.Level[gTheGame.CurrentPlayer] && MoveIsKO (m, level, player)))
                        {
                            if (whatIfResult > maxSoFar)    //    best move so far!
                                * ((long *) move) = * ((long *) (& m));

                            if (AlfaBeta (player, whatIfResult, &minSoFar, &maxSoFar, &alfa, &beta))
                                return player == gTheGame.CurrentPlayer ? minSoFar : maxSoFar;
                        }
                    }
                }

            //    if there is a third ball for this fliche, try the fliche of length 3 as well

                if (! m[2])        //    Wait a minute! Didn't we just do this ?
                {
                    m[2] = Neighbour (m[1], df);

                    if (board->field[m[2]] == player)    //    a fliche of length 3 in this direction
                        goto try_fliche_3_1;

                }
            }
        }
    }
    return maxSoFar;
}



short
FindBestMove (BoardPtr board, MoveJudgeProc judgemove, short player, MovePtr move, short level, short alfa, short beta)
{
    MoveData            m;
    register short        df;
    short                minSoFar = kMaxJudgeVal;
    short                maxSoFar = kMinJudgeVal;

    Board                whatIfBoard;
    short                whatIfResult;

    * ((long *) move) = 0L;

    for (m[0] = 1; m[0] <= kFields; m[0]++)
    {
        if (board->field[m[0]] != player)
            continue;

        if (level == 1)
            SystemTime();

        for (m[3] = right; m[3] < down; m[3]++)
        {
            m[1] = 0;

            if (ValidMove (board, m))
            {
                whatIfResult = (*judgemove) (board, player, m);
                if (level > 0)
                {
                    CopyBoard (board, & whatIfBoard);
                    (void) DoMove (& whatIfBoard, m);
                    whatIfResult -= FindBestMove (    & whatIfBoard,
                                                        judgemove,
                                                        NextPlayer (player),
                                                        scratch,
                                                        level - 1,
                                                        player == gTheGame.CurrentPlayer ? maxSoFar : alfa,
                                                        player == gTheGame.CurrentPlayer ? beta : minSoFar
                                                    );
                }
                if (whatIfResult > maxSoFar)
                {
                    if (! (level == gSet.Level[gTheGame.CurrentPlayer] && MoveIsKO (m, level, player)))
                    {
                        if (whatIfResult > maxSoFar)    //    best move so far!
                            * ((long *) move) = * ((long *) (& m));

                        if (AlfaBeta (player, whatIfResult, &minSoFar, &maxSoFar, &alfa, &beta))
                            return player == gTheGame.CurrentPlayer ? minSoFar : maxSoFar;
                    }
                }
            }

            for (df = right; df < left; df++)
            {
                if (m[3] == df || m[3] == df + 3)
                    continue;

                m[1] = Neighbour (m[0], df);

                if (board->field[m[1]] != player)
                    continue;

                m[2] = empty;

                if (ValidFlicheMoveSorted (board, m))
                {
                    whatIfResult = (*judgemove) (board, player, m);
                    if (level > 0)
                    {
                        CopyBoard (board, & whatIfBoard);
                        (void) DoFlicheMove (& whatIfBoard, m);
                        whatIfResult -= FindBestMove (    & whatIfBoard,
                                                            judgemove,
                                                            NextPlayer (player),
                                                            scratch,
                                                            level - 1,
                                                            player == gTheGame.CurrentPlayer ? maxSoFar : alfa,
                                                            player == gTheGame.CurrentPlayer ? beta : minSoFar
                                                        );
                    }
                    if (whatIfResult > maxSoFar)
                    {
                        if (! (level == gSet.Level[gTheGame.CurrentPlayer] && MoveIsKO (m, level, player)))
                        {
                            if (whatIfResult > maxSoFar)
                                * ((long *) move) = * ((long *) (& m));

                            if (AlfaBeta (player, whatIfResult, &minSoFar, &maxSoFar, &alfa, &beta))
                                return player == gTheGame.CurrentPlayer ? minSoFar : maxSoFar;
                        }
                    }
                }

                m[2] = Neighbour (m[1], df);

                if (board->field[m[2]] != player)
                    continue;

                if (ValidFlicheMoveSorted (board, m))
                {
                    whatIfResult = (*judgemove) (board, player, m);
                    if (level > 0)
                    {
                        CopyBoard (board, & whatIfBoard);
                        (void) DoFlicheMove (& whatIfBoard, m);
                        whatIfResult -= FindBestMove (    & whatIfBoard,
                                                            judgemove,
                                                            NextPlayer (player),
                                                            scratch,
                                                            level - 1,
                                                            player == gTheGame.CurrentPlayer ? maxSoFar : alfa,
                                                            player == gTheGame.CurrentPlayer ? beta : minSoFar
                                                        );
                    }
                    if (whatIfResult > maxSoFar)
                    {
                        if (! (level == gSet.Level[gTheGame.CurrentPlayer] && MoveIsKO (m, level, player)))
                        {
                            if (whatIfResult > maxSoFar)
                                * ((long *) move) = * ((long *) (& m));

                            if (AlfaBeta (player, whatIfResult, &minSoFar, &maxSoFar, &alfa, &beta))
                                return player == gTheGame.CurrentPlayer ? minSoFar : maxSoFar;
                        }
                    }
                }
            }
        }
    }
    return maxSoFar;
}



Boolean
AlfaBeta (short player, short value, short *min, short *max, short *alfa, short *beta)
{
    if (value > *max)
        *max = value;

    if (value < *min)
        *min = value;

    if (player == gTheGame.CurrentPlayer)
    {
        if (*max > *alfa)
            *alfa = *max;

        return (*max > *beta);
    }
    else
    {
        if (*min < *beta)
            *beta = *min;

        return (*min < *alfa);
    }
}

//static unsigned char spiral_in [kFields+1] =
//{
//    1,    2,    3,    4,    5,    11,    18,    26,    35,    43,    50,    56,    61,
//    60,    59,    58,    57,    51,    44,    36,    27,    19,    12,    6,    7,    8,    9,
//    10,    17,    25,    34,    42,    49,    55,    54,    53,    52,    45,    37,    28,    20,
//    13,    14,    15,    16,    24,    33,    41,    48,    47,    46,    38,    29,    21,    22,
//    23,    32,    40,    39,    30,    31, 0    //    0 = sentinel
//};

//static Field spiral_out [kFields+1] =
//{
//    31, 30, 39, 40, 32, 23, 22, 21, 29, 38, 46, 47, 48,
//    41, 33, 24, 16, 15, 14, 13, 20, 28, 37, 45, 52, 53, 54,
//    55, 49, 42, 34, 25, 17, 10,  9,  8,  7,  6, 12, 19, 27,
//    36, 44, 51, 57, 58, 59, 60, 61, 56, 50, 43, 35, 26, 18,
//    11,  5,  4,  3,  2,  1, 0    //    0 = sentinel
//};


//Boolean
//PlayerHasBallOnOuterRing (BoardPtr board, short player)
//{
//    static Field outer_ring [25] =
//    {
//        1,    2,    3,    4,    5,    11,    18,    26,    35,    43,    50,    56,    61,
//        60,    59,    58,    57,    51,    44,    36,    27,    19,    12,    6, 0
//    };
//    register FieldsPtr    fp, rp;
//
//    for (fp = board->field, rp = outer_ring; *rp; rp++)
//        if (*(fp + *rp) == player)
//            return true;
//
//    return false;
//}